#include <bits/stdc++.h>
// 2025/07/10
// tag:
// Author: Forever
using namespace std;
using int64 = int64_t;
#define int long long
const int N = 100001;

int n, m, cnt, dfn[N], low[N], sz[N], belong[N], in[N], dp[N], idx, sc;
struct {
    int x, y, z;
} e[N];
bool vis[N];
stack<int> st;
vector<int> edge[N];
vector<pair<int, int>> edge2[N];

void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++idx, st.push(u), vis[u] = true;
    for (int x : edge[u]) {
        if (!dfn[x]) {
            tarjan(x, u);
            low[u] = min(low[u], low[x]);
        } else if (vis[x])
            low[u] = min(low[u], dfn[x]);
    }
    if (dfn[u] == low[u]) {
        ++sc;
        while (st.top() != u) {
            sz[sc]++;
            vis[st.top()] = false;
            belong[st.top()] = sc;
            st.pop();
        }
        sz[sc]++, vis[u] = false, belong[u] = sc;
        st.pop();
    }
}

void topo()
{
    queue<int> q;
    for (int i = 1; i <= sc; i++)
        if (!in[i])
            q.push(i), dp[i] = 1;
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        cnt++;
        for (auto x : edge2[s]) {
            dp[x.first] = max(dp[x.first], dp[s] + x.second);
            if (--in[x.first] == 0)
                q.push(x.first);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> e[i].x >> e[i].y >> e[i].z;
    for (int i = 1; i <= m; i++) {
        if (e[i].x == 1)
            edge[e[i].y].push_back(e[i].z), edge[e[i].z].push_back(e[i].y);
        if (e[i].x == 3)
            edge[e[i].z].push_back(e[i].y);
        if (e[i].x == 5)
            edge[e[i].y].push_back(e[i].z);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            idx = 0, tarjan(i, i);
    for (int i = 1; i <= m; i++) {
        int x = e[i].x, y = e[i].y, z = e[i].z;
        int by = belong[y], bz = belong[z];
        if (x == 2)
            edge2[by].push_back(make_pair(bz, 1)), in[bz]++;
        else if (x == 4)
            edge2[bz].push_back(make_pair(by, 1)), in[by]++;
        if (bz != by) {
            if (x == 3)
                edge2[bz].push_back(make_pair(by, 0)), in[by]++;
            else if (x == 5)
                edge2[by].push_back(make_pair(bz, 0)), in[bz]++;
        }
    }
    topo();
    if (cnt < sc) {
        cout << -1 << endl;
        return 0;
    }
    int ans = 0;
    for (int i = 1; i <= sc; i++)
        ans += sz[i] * dp[i];
    cout << ans << endl;
    return 0;
}